#include<bits/stdc++.h>
using namespace std;
int n,a[10010],u,v,ans,y[10010],h[10010],now[10010];
vector<int> edge[10010];
const int mod=111121;
int ksm(int x,int y){
	long long res=1,now=x;
	while(y){
		if(y&1) res*=now,res%=mod;
		now*=now,now%=mod,y>>=1;
	}
	return res;
}
void dfs(int u,int f,int z){
	y[u]=(y[f]&a[u]),h[u]=(h[f]|a[u]);
	if(y[u]!=y[f]||h[u]!=h[f]) now[u]=ksm(y[u],h[u]);
	else now[u]=now[f];
	if(u>=z) ans+=now[u],ans%=mod;
	for(auto &i:edge[u])
		if(i!=f) dfs(i,u,z);
}
int main(){
	freopen("abstract.in","r",stdin);
	freopen("abstract.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		edge[u].push_back(v),edge[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		y[0]=a[i];
		dfs(i,0,i);
	}
	printf("%d",ans);
	return 0;
}
